package org.example.string;

/**
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 *
 * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
 * 示例 :
 *
 * 输入: num1 = "123", num2 = "456"
 * 输出: "56088"
 */
public class Multiply {
    public String multiply(String num1, String num2) {
        //先计算无进位乘法，最后处理进位
        int n = num1.length(),m = num2.length();
        char[] s1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] s2 = new StringBuffer(num2).reverse().toString().toCharArray();
        int[] tmp = new int[m+n-1];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                tmp[i+j]+=(s1[i]-'0') * (s2[j] - '0');
            }
        }
        //处理进位
        StringBuffer ret = new StringBuffer();
        int cur=0,t=0;
        while(cur < m+n-1 || t!=0){
            if(cur < m+n-1) t+=tmp[cur++];
            ret.append((char)(t%10+'0'));
            t/=10;
        }
        while(ret.length()>1 && ret.charAt(ret.length()-1)=='0'){
            ret.deleteCharAt(ret.length()-1);
        }
        return ret.reverse().toString();
    }
}
